package leetcode;

import java.util.*;

/**
 * 描述:257. 二叉树的所有路径
 *
 * @author Madison You
 * @created 21:48
 */
public class Easy_257_BinaryTreePaths {
    public static void main(String[] args) {
        Integer[] integers = {1, 2, 3, null, 5};
        TreeNode treeNode = CreateTreeNode.arrayToTreeNode(integers);
        new Easy_257_BinaryTreePaths().binaryTreePaths1(treeNode);
    }

    public List<String> binaryTreePaths(TreeNode root) {
        Deque<Object> deque = new LinkedList<>();
        List<String> list = new ArrayList<>();
        if (root == null) return list;
        deque.push(root);
        deque.push(root.val + "");
        while (!deque.isEmpty()) {
            String str = (String) deque.pop();
            TreeNode node = (TreeNode) deque.pop();
            if (node.left == null && node.right == null) {
                list.add(str);
            }
            if (node.right != null) {
                deque.push(node.right);
                deque.push(str + "->" + node.right.val);
            }
            if (node.left != null) {
                deque.push(node.left);
                deque.push(str + "->" + node.left.val);
            }
        }
        return list;
    }

    public List<String> binaryTreePaths1(TreeNode root) {
        List<String> lists = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        back(lists, list, root);
        return lists;
    }

    private void back(List<String> lists, List<Integer> list, TreeNode root) {
        list.add(root.val);
        if (root.left == null && root.right == null) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < list.size(); i++) {
                sb.append(list.get(i));
                if (i < list.size() - 1) {
                    sb.append("->");
                }
            }
            lists.add(sb.toString());
        }

        if (root.left != null) {
            back(lists, list, root.left);
            list.remove(list.size() - 1);
        }

        if (root.right != null) {
            back(lists, list, root.right);
            list.remove(list.size() - 1);
        }

    }
}
